#include <iostream>
#include <vector>

using namespace std;
// 归并排序

// 归并
void merge(vector<int>& arr, int L, int M, int R)
{
  int LEFT_SIZE = M - L;  // 左边子串的长度
  int RIGHT_SIZE =
      R - M + 1;  // 右边子串的长度:跟主函数的传参有关，因为传的是右区间[M+1,R]：R-(M+1)+1对应本code
  int left[LEFT_SIZE];  // 需要新开辟数组空间
  int right[RIGHT_SIZE];

  int i, j, k;

  // 1.Fill in the left sub array 把数组arr的数分别填到左右子串
  for (i = L; i < M; i++)
  {
    left[i - L] = arr[i];
  }
  // 1.Fill in the right sub array 把数组arr的数分别填到左右子串
  for (j = M; i <= R; i++)
  {
    right[i - M] = arr[i];
  }

  // 2. 左右两个left right数组进行合并,三个指针分别指向左右子串以及新开辟的大数组
  i = 0;
  j = 0;
  k = L;  // 定义指向左右子串以及要归并到的大数组arr的指针

  // 当左右指针不越界时
  // 开始归并
  while (i < LEFT_SIZE && j < RIGHT_SIZE)
  {
    // 因左边子串指针指向的元素小于右边的指针指向的
    // 左边的元素填到大数组
    // 左边指针前进，大数组指针前进
    if (left[i] < right[j])
    {
      // 可以说是对arr[]中的值全都重新覆盖
      arr[k] = left[i];
      i++;
      k++;
    }
    // 若右边子串指针指向的元素更小
    // 执行相同操作
    else
    {
      arr[k] = right[j];
      j++;
      k++;
    }
  }

  // 经过上一个循环，左右子串有一方指针先到达数组尾哨兵处，另一边的数组直接添加到大数组末尾
  // 若j先到达尾哨兵
  while (i < LEFT_SIZE)
  {
    arr[k] = left[i];
    i++;
    k++;
  }

  // 若i先到达尾哨兵
  while (j < LEFT_SIZE)
  {
    arr[k] = right[j];
    j++;
    k++;
  }
}

// 分治
void mergeSort(vector<int>& arr, int L, int R)
{
  // base case:分治到不能再分
  if (L == R)
  {
    return;
  }

  // 首先把这个长的数组，砍成两半
  int M = (L + R) / 2;
  // 二分分治
  // 继续把左边这一半分治
  mergeSort(arr, L, M);
  // 继续把右边这一半分治
  mergeSort(arr, M + 1, R);

  // 把左右有序子串，归并
  merge(arr, L, M + 1, R);  // 这里的M要和merge()中的M对应，merge()函数中M是上取整,所以这里+1
}

int main()
{
  // 验证归并
  /*
  vector<int> arr = {2, 8, 9, 10, 4, 5, 6, 7};
  int L = 0;
  int R = 7;
  int M = 4; // 上取整
  merge(arr, L, M, R);
  */

  // 验证归并排序：左右两个子串不是有序，先分治
  vector<int> arr = {2, 9, 8, 10, 4, 6, 5, 7};
  int L = 0;
  int R = 7;
  int M = 4;  // 上取整
  mergeSort(arr, L, R);

  return 0;
}